home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 10 / AACD 10.iso / AACD / Games / WarpQuake / Src / world.c < prev    next >
C/C++ Source or Header  |  2000-05-22  |  22KB  |  963 lines
  1. /*
  2. Copyright (C) 1996-1997 Id Software, Inc.
  3.  
  4. This program is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU General Public License
  6. as published by the Free Software Foundation; either version 2
  7. of the License, or (at your option) any later version.
  8.  
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  12.  
  13. See the GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18.  
  19. */
  20. // world.c -- world query functions
  21.  
  22. #include "quakedef.h"
  23.  
  24. /*
  25.  
  26. entities never clip against themselves, or their owner
  27.  
  28. line of sight checks trace->crosscontent, but bullets don't
  29.  
  30. */
  31.  
  32.  
  33. typedef struct
  34. {
  35.     vec3_t        boxmins, boxmaxs;// enclose the test object along entire move
  36.     float        *mins, *maxs;    // size of the moving object
  37.     vec3_t        mins2, maxs2;    // size when clipping against mosnters
  38.     float        *start, *end;
  39.     trace_t        trace;
  40.     int            type;
  41.     edict_t        *passedict;
  42. } moveclip_t;
  43.  
  44.  
  45. int SV_HullPointContents (hull_t *hull, int num, vec3_t p);
  46.  
  47. /*
  48. ===============================================================================
  49.  
  50. HULL BOXES
  51.  
  52. ===============================================================================
  53. */
  54.  
  55.  
  56. static    hull_t        box_hull;
  57. static    dclipnode_t    box_clipnodes[6];
  58. static    mplane_t    box_planes[6];
  59.  
  60. /*
  61. ===================
  62. SV_InitBoxHull
  63.  
  64. Set up the planes and clipnodes so that the six floats of a bounding box
  65. can just be stored out and get a proper hull_t structure.
  66. ===================
  67. */
  68. void SV_InitBoxHull (void)
  69. {
  70.     int        i;
  71.     int        side;
  72.  
  73.     box_hull.clipnodes = box_clipnodes;
  74.     box_hull.planes = box_planes;
  75.     box_hull.firstclipnode = 0;
  76.     box_hull.lastclipnode = 5;
  77.  
  78.     for (i=0 ; i<6 ; i++)
  79.     {
  80.         box_clipnodes[i].planenum = i;
  81.         
  82.         side = i&1;
  83.         
  84.         box_clipnodes[i].children[side] = CONTENTS_EMPTY;
  85.         if (i != 5)
  86.             box_clipnodes[i].children[side^1] = i + 1;
  87.         else
  88.             box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
  89.         
  90.         box_planes[i].type = i>>1;
  91.         box_planes[i].normal[i>>1] = 1;
  92.     }
  93.     
  94. }
  95.  
  96.  
  97. /*
  98. ===================
  99. SV_HullForBox
  100.  
  101. To keep everything totally uniform, bounding boxes are turned into small
  102. BSP trees instead of being compared directly.
  103. ===================
  104. */
  105. hull_t    *SV_HullForBox (vec3_t mins, vec3_t maxs)
  106. {
  107.     box_planes[0].dist = maxs[0];
  108.     box_planes[1].dist = mins[0];
  109.     box_planes[2].dist = maxs[1];
  110.     box_planes[3].dist = mins[1];
  111.     box_planes[4].dist = maxs[2];
  112.     box_planes[5].dist = mins[2];
  113.  
  114.     return &box_hull;
  115. }
  116.  
  117.  
  118.  
  119. /*
  120. ================
  121. SV_HullForEntity
  122.  
  123. Returns a hull that can be used for testing or clipping an object of mins/maxs
  124. size.
  125. Offset is filled in to contain the adjustment that must be added to the
  126. testing object's origin to get a point to use with the returned hull.
  127. ================
  128. */
  129. hull_t *SV_HullForEntity (edict_t *ent, vec3_t mins, vec3_t maxs, vec3_t offset)
  130. {
  131.     model_t        *model;
  132.     vec3_t        size;
  133.     vec3_t        hullmins, hullmaxs;
  134.     hull_t        *hull;
  135.  
  136. // decide which clipping hull to use, based on the size
  137.     if (ent->v.solid == SOLID_BSP)
  138.     {    // explicit hulls in the BSP model
  139.         if (ent->v.movetype != MOVETYPE_PUSH)
  140.             Sys_Error ("SOLID_BSP without MOVETYPE_PUSH");
  141.  
  142.         model = sv.models[ (int)ent->v.modelindex ];
  143.  
  144.         if (!model || model->type != mod_brush)
  145.             Sys_Error ("MOVETYPE_PUSH with a non bsp model");
  146.  
  147.         VectorSubtract (maxs, mins, size);
  148.         if (size[0] < 3)
  149.             hull = &model->hulls[0];
  150.         else if (size[0] <= 32)
  151.             hull = &model->hulls[1];
  152.         else
  153.             hull = &model->hulls[2];
  154.  
  155. // calculate an offset value to center the origin
  156.         VectorSubtract (hull->clip_mins, mins, offset);
  157.         VectorAdd (offset, ent->v.origin, offset);
  158.     }
  159.     else
  160.     {    // create a temp hull from bounding box sizes
  161.  
  162.         VectorSubtract (ent->v.mins, maxs, hullmins);
  163.         VectorSubtract (ent->v.maxs, mins, hullmaxs);
  164.         hull = SV_HullForBox (hullmins, hullmaxs);
  165.         
  166.         VectorCopy (ent->v.origin, offset);
  167.     }
  168.  
  169.  
  170.     return hull;
  171. }
  172.  
  173. /*
  174. ===============================================================================
  175.  
  176. ENTITY AREA CHECKING
  177.  
  178. ===============================================================================
  179. */
  180.  
  181. typedef struct areanode_s
  182. {
  183.     int        axis;        // -1 = leaf node
  184.     float    dist;
  185.     struct areanode_s    *children[2];
  186.     link_t    trigger_edicts;
  187.     link_t    solid_edicts;
  188. } areanode_t;
  189.  
  190. #define    AREA_DEPTH    4
  191. #define    AREA_NODES    32
  192.  
  193. static    areanode_t    sv_areanodes[AREA_NODES];
  194. static    int            sv_numareanodes;
  195.  
  196. /*
  197. ===============
  198. SV_CreateAreaNode
  199.  
  200. ===============
  201. */
  202. areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
  203. {
  204.     areanode_t    *anode;
  205.     vec3_t        size;
  206.     vec3_t        mins1, maxs1, mins2, maxs2;
  207.  
  208.     anode = &sv_areanodes[sv_numareanodes];
  209.     sv_numareanodes++;
  210.  
  211.     ClearLink (&anode->trigger_edicts);
  212.     ClearLink (&anode->solid_edicts);
  213.     
  214.     if (depth == AREA_DEPTH)
  215.     {
  216.         anode->axis = -1;
  217.         anode->children[0] = anode->children[1] = NULL;
  218.         return anode;
  219.     }
  220.     
  221.     VectorSubtract (maxs, mins, size);
  222.     if (size[0] > size[1])
  223.         anode->axis = 0;
  224.     else
  225.         anode->axis = 1;
  226.     
  227.     anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
  228.     VectorCopy (mins, mins1);    
  229.     VectorCopy (mins, mins2);    
  230.     VectorCopy (maxs, maxs1);    
  231.     VectorCopy (maxs, maxs2);    
  232.     
  233.     maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
  234.     
  235.     anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
  236.     anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
  237.  
  238.     return anode;
  239. }
  240.  
  241. /*
  242. ===============
  243. SV_ClearWorld
  244.  
  245. ===============
  246. */
  247. void SV_ClearWorld (void)
  248. {
  249.     SV_InitBoxHull ();
  250.     
  251.     memset (sv_areanodes, 0, sizeof(sv_areanodes));
  252.     sv_numareanodes = 0;
  253.     SV_CreateAreaNode (0, sv.worldmodel->mins, sv.worldmodel->maxs);
  254. }
  255.  
  256.  
  257. /*
  258. ===============
  259. SV_UnlinkEdict
  260.  
  261. ===============
  262. */
  263. void SV_UnlinkEdict (edict_t *ent)
  264. {
  265.     if (!ent->area.prev)
  266.         return;        // not linked in anywhere
  267.     RemoveLink (&ent->area);
  268.     ent->area.prev = ent->area.next = NULL;
  269. }
  270.  
  271.  
  272. /*
  273. ====================
  274. SV_TouchLinks
  275. ====================
  276. */
  277. void SV_TouchLinks ( edict_t *ent, areanode_t *node )
  278. {
  279.     link_t        *l, *next;
  280.     edict_t        *touch;
  281.     int            old_self, old_other;
  282.  
  283. // touch linked edicts
  284.     for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
  285.     {
  286.         next = l->next;
  287.         touch = EDICT_FROM_AREA(l);
  288.         if (touch == ent)
  289.             continue;
  290.         if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
  291.             continue;
  292.         if (ent->v.absmin[0] > touch->v.absmax[0]
  293.         || ent->v.absmin[1] > touch->v.absmax[1]
  294.         || ent->v.absmin[2] > touch->v.absmax[2]
  295.         || ent->v.absmax[0] < touch->v.absmin[0]
  296.         || ent->v.absmax[1] < touch->v.absmin[1]
  297.         || ent->v.absmax[2] < touch->v.absmin[2] )
  298.             continue;
  299.         old_self = pr_global_struct->self;
  300.         old_other = pr_global_struct->other;
  301.  
  302.         pr_global_struct->self = EDICT_TO_PROG(touch);
  303.         pr_global_struct->other = EDICT_TO_PROG(ent);
  304.         pr_global_struct->time = sv.time;
  305.         PR_ExecuteProgram (touch->v.touch);
  306.  
  307.         pr_global_struct->self = old_self;
  308.         pr_global_struct->other = old_other;
  309.     }
  310.     
  311. // recurse down both sides
  312.     if (node->axis == -1)
  313.         return;
  314.     
  315.     if ( ent->v.absmax[node->axis] > node->dist )
  316.         SV_TouchLinks ( ent, node->children[0] );
  317.     if ( ent->v.absmin[node->axis] < node->dist )
  318.         SV_TouchLinks ( ent, node->children[1] );
  319. }
  320.  
  321.  
  322. /*
  323. ===============
  324. SV_FindTouchedLeafs
  325.  
  326. ===============
  327. */
  328. void SV_FindTouchedLeafs (edict_t *ent, mnode_t *node)
  329. {
  330.     mplane_t    *splitplane;
  331.     mleaf_t        *leaf;
  332.     int            sides;
  333.     int            leafnum;
  334.  
  335.     if (node->contents == CONTENTS_SOLID)
  336.         return;
  337.     
  338. // add an efrag if the node is a leaf
  339.  
  340.     if ( node->contents < 0)
  341.     {
  342.         if (ent->num_leafs == MAX_ENT_LEAFS)
  343.             return;
  344.  
  345.         leaf = (mleaf_t *)node;
  346.         leafnum = leaf - sv.worldmodel->leafs - 1;
  347.  
  348.         ent->leafnums[ent->num_leafs] = leafnum;
  349.         ent->num_leafs++;            
  350.         return;
  351.     }
  352.     
  353. // NODE_MIXED
  354.  
  355.     splitplane = node->plane;
  356.     sides = BOX_ON_PLANE_SIDE(ent->v.absmin, ent->v.absmax, splitplane);
  357.     
  358. // recurse down the contacted sides
  359.     if (sides & 1)
  360.         SV_FindTouchedLeafs (ent, node->children[0]);
  361.         
  362.     if (sides & 2)
  363.         SV_FindTouchedLeafs (ent, node->children[1]);
  364. }
  365.  
  366. /*
  367. ===============
  368. SV_LinkEdict
  369.  
  370. ===============
  371. */
  372. void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
  373. {
  374.     areanode_t    *node;
  375.  
  376.     if (ent->area.prev)
  377.         SV_UnlinkEdict (ent);    // unlink from old position
  378.         
  379.     if (ent == sv.edicts)
  380.         return;        // don't add the world
  381.  
  382.     if (ent->free)
  383.         return;
  384.  
  385. // set the abs box
  386.  
  387. #ifdef QUAKE2
  388.     if (ent->v.solid == SOLID_BSP && 
  389.     (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]) )
  390.     {    // expand for rotation
  391.         float        max, v;
  392.         int            i;
  393.  
  394.         max = 0;
  395.         for (i=0 ; i<3 ; i++)
  396.         {
  397.             v =fabs( ent->v.mins[i]);
  398.             if (v > max)
  399.                 max = v;
  400.             v =fabs( ent->v.maxs[i]);
  401.             if (v > max)
  402.                 max = v;
  403.         }
  404.         for (i=0 ; i<3 ; i++)
  405.         {
  406.             ent->v.absmin[i] = ent->v.origin[i] - max;
  407.             ent->v.absmax[i] = ent->v.origin[i] + max;
  408.         }
  409.     }
  410.     else
  411. #endif
  412.     {
  413.         VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);    
  414.         VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
  415.     }
  416.  
  417. //
  418. // to make items easier to pick up and allow them to be grabbed off
  419. // of shelves, the abs sizes are expanded
  420. //
  421.     if ((int)ent->v.flags & FL_ITEM)
  422.     {
  423.         ent->v.absmin[0] -= 15;
  424.         ent->v.absmin[1] -= 15;
  425.         ent->v.absmax[0] += 15;
  426.         ent->v.absmax[1] += 15;
  427.     }
  428.     else
  429.     {    // because movement is clipped an epsilon away from an actual edge,
  430.         // we must fully check even when bounding boxes don't quite touch
  431.         ent->v.absmin[0] -= 1;
  432.         ent->v.absmin[1] -= 1;
  433.         ent->v.absmin[2] -= 1;
  434.         ent->v.absmax[0] += 1;
  435.         ent->v.absmax[1] += 1;
  436.         ent->v.absmax[2] += 1;
  437.     }
  438.     
  439. // link to PVS leafs
  440.     ent->num_leafs = 0;
  441.     if (ent->v.modelindex)
  442.         SV_FindTouchedLeafs (ent, sv.worldmodel->nodes);
  443.  
  444.     if (ent->v.solid == SOLID_NOT)
  445.         return;
  446.  
  447. // find the first node that the ent's box crosses
  448.     node = sv_areanodes;
  449.     while (1)
  450.     {
  451.         if (node->axis == -1)
  452.             break;
  453.         if (ent->v.absmin[node->axis] > node->dist)
  454.             node = node->children[0];
  455.         else if (ent->v.absmax[node->axis] < node->dist)
  456.             node = node->children[1];
  457.         else
  458.             break;        // crosses the node
  459.     }
  460.     
  461. // link it in    
  462.  
  463.     if (ent->v.solid == SOLID_TRIGGER)
  464.         InsertLinkBefore (&ent->area, &node->trigger_edicts);
  465.     else
  466.         InsertLinkBefore (&ent->area, &node->solid_edicts);
  467.     
  468. // if touch_triggers, touch all entities at this node and decend for more
  469.     if (touch_triggers)
  470.         SV_TouchLinks ( ent, sv_areanodes );
  471. }
  472.  
  473.  
  474.  
  475. /*
  476. ===============================================================================
  477.  
  478. POINT TESTING IN HULLS
  479.  
  480. ===============================================================================
  481. */
  482.  
  483. #if    !id386
  484.  
  485. /*
  486. ==================
  487. SV_HullPointContents
  488.  
  489. ==================
  490. */
  491. int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
  492. {
  493.     float        d;
  494.     dclipnode_t    *node;
  495.     mplane_t    *plane;
  496.  
  497.     while (num >= 0)
  498.     {
  499.         if (num < hull->firstclipnode || num > hull->lastclipnode)
  500.             Sys_Error ("SV_HullPointContents: bad node number");
  501.     
  502.         node = hull->clipnodes + num;
  503.         plane = hull->planes + node->planenum;
  504.         
  505.         if (plane->type < 3)
  506.             d = p[plane->type] - plane->dist;
  507.         else
  508.             d = DotProduct (plane->normal, p) - plane->dist;
  509.         if (d < 0)
  510.             num = node->children[1];
  511.         else
  512.             num = node->children[0];
  513.     }
  514.     
  515.     return num;
  516. }
  517.  
  518. #endif    // !id386
  519.  
  520.  
  521. /*
  522. ==================
  523. SV_PointContents
  524.  
  525. ==================
  526. */
  527. int SV_PointContents (vec3_t p)
  528. {
  529.     int        cont;
  530.  
  531.     cont = SV_HullPointContents (&sv.worldmodel->hulls[0], 0, p);
  532.     if (cont <= CONTENTS_CURRENT_0 && cont >= CONTENTS_CURRENT_DOWN)
  533.         cont = CONTENTS_WATER;
  534.     return cont;
  535. }
  536.  
  537. int SV_TruePointContents (vec3_t p)
  538. {
  539.     return SV_HullPointContents (&sv.worldmodel->hulls[0], 0, p);
  540. }
  541.  
  542. //===========================================================================
  543.  
  544. /*
  545. ============
  546. SV_TestEntityPosition
  547.  
  548. This could be a lot more efficient...
  549. ============
  550. */
  551. edict_t    *SV_TestEntityPosition (edict_t *ent)
  552. {
  553.     trace_t    trace;
  554.  
  555.     trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, 0, ent);
  556.     
  557.     if (trace.startsolid)
  558.         return sv.edicts;
  559.         
  560.     return NULL;
  561. }
  562.  
  563.  
  564. /*
  565. ===============================================================================
  566.  
  567. LINE TESTING IN HULLS
  568.  
  569. ===============================================================================
  570. */
  571.  
  572. // 1/32 epsilon to keep floating point happy
  573. #define    DIST_EPSILON    (0.03125)
  574.  
  575. /*
  576. ==================
  577. SV_RecursiveHullCheck
  578.  
  579. ==================
  580. */
  581. qboolean SV_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, trace_t *trace)
  582. {
  583.     dclipnode_t    *node;
  584.     mplane_t    *plane;
  585.     float        t1, t2;
  586.     float        frac;
  587.     int            i;
  588.     vec3_t        mid;
  589.     int            side;
  590.     float        midf;
  591.  
  592. // check for empty
  593.     if (num < 0)
  594.     {
  595.         if (num != CONTENTS_SOLID)
  596.         {
  597.             trace->allsolid = false;
  598.             if (num == CONTENTS_EMPTY)
  599.                 trace->inopen = true;
  600.             else
  601.                 trace->inwater = true;
  602.         }
  603.         else
  604.             trace->startsolid = true;
  605.         return true;        // empty
  606.     }
  607.  
  608.     if (num < hull->firstclipnode || num > hull->lastclipnode)
  609.         Sys_Error ("SV_RecursiveHullCheck: bad node number");
  610.  
  611. //
  612. // find the point distances
  613. //
  614.     node = hull->clipnodes + num;
  615.     plane = hull->planes + node->planenum;
  616.  
  617.     if (plane->type < 3)
  618.     {
  619.         t1 = p1[plane->type] - plane->dist;
  620.         t2 = p2[plane->type] - plane->dist;
  621.     }
  622.     else
  623.     {
  624.         t1 = DotProduct (plane->normal, p1) - plane->dist;
  625.         t2 = DotProduct (plane->normal, p2) - plane->dist;
  626.     }
  627.     
  628. #if 1
  629.     if (t1 >= 0 && t2 >= 0)
  630.         return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
  631.     if (t1 < 0 && t2 < 0)
  632.         return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
  633. #else
  634.     if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
  635.         return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
  636.     if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
  637.         return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
  638. #endif
  639.  
  640. // put the crosspoint DIST_EPSILON pixels on the near side
  641.     if (t1 < 0)
  642.         frac = (t1 + DIST_EPSILON)/(t1-t2);
  643.     else
  644.         frac = (t1 - DIST_EPSILON)/(t1-t2);
  645.     if (frac < 0)
  646.         frac = 0;
  647.     if (frac > 1)
  648.         frac = 1;
  649.         
  650.     midf = p1f + (p2f - p1f)*frac;
  651.     for (i=0 ; i<3 ; i++)
  652.         mid[i] = p1[i] + frac*(p2[i] - p1[i]);
  653.  
  654.     side = (t1 < 0);
  655.  
  656. // move up to the node
  657.     if (!SV_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
  658.         return false;
  659.  
  660. #ifdef PARANOID
  661.     if (SV_HullPointContents (sv_hullmodel, mid, node->children[side])
  662.     == CONTENTS_SOLID)
  663.     {
  664.         Con_Printf ("mid PointInHullSolid\n");
  665.         return false;
  666.     }
  667. #endif
  668.     
  669.     if (SV_HullPointContents (hull, node->children[side^1], mid)
  670.     != CONTENTS_SOLID)
  671. // go past the node
  672.         return SV_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
  673.     
  674.     if (trace->allsolid)
  675.         return false;        // never got out of the solid area
  676.         
  677. //==================
  678. // the other side of the node is solid, this is the impact point
  679. //==================
  680.     if (!side)
  681.     {
  682.         VectorCopy (plane->normal, trace->plane.normal);
  683.         trace->plane.dist = plane->dist;
  684.     }
  685.     else
  686.     {
  687.         VectorSubtract (vec3_origin, plane->normal, trace->plane.normal);
  688.         trace->plane.dist = -plane->dist;
  689.     }
  690.  
  691.     while (SV_HullPointContents (hull, hull->firstclipnode, mid)
  692.     == CONTENTS_SOLID)
  693.     { // shouldn't really happen, but does occasionally
  694.         frac -= 0.1;
  695.         if (frac < 0)
  696.         {
  697.             trace->fraction = midf;
  698.             VectorCopy (mid, trace->endpos);
  699.             Con_DPrintf ("backup past 0\n");
  700.             return false;
  701.         }
  702.         midf = p1f + (p2f - p1f)*frac;
  703.         for (i=0 ; i<3 ; i++)
  704.             mid[i] = p1[i] + frac*(p2[i] - p1[i]);
  705.     }
  706.  
  707.     trace->fraction = midf;
  708.     VectorCopy (mid, trace->endpos);
  709.  
  710.     return false;
  711. }
  712.  
  713.  
  714. /*
  715. ==================
  716. SV_ClipMoveToEntity
  717.  
  718. Handles selection or creation of a clipping hull, and offseting (and
  719. eventually rotation) of the end points
  720. ==================
  721. */
  722. trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
  723. {
  724.     trace_t        trace;
  725.     vec3_t        offset;
  726.     vec3_t        start_l, end_l;
  727.     hull_t        *hull;
  728.  
  729. // fill in a default trace
  730.     memset (&trace, 0, sizeof(trace_t));
  731.     trace.fraction = 1;
  732.     trace.allsolid = true;
  733.     VectorCopy (end, trace.endpos);
  734.  
  735. // get the clipping hull
  736.     hull = SV_HullForEntity (ent, mins, maxs, offset);
  737.  
  738.     VectorSubtract (start, offset, start_l);
  739.     VectorSubtract (end, offset, end_l);
  740.  
  741. #ifdef QUAKE2
  742.     // rotate start and end into the models frame of reference
  743.     if (ent->v.solid == SOLID_BSP && 
  744.     (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]) )
  745.     {
  746.         vec3_t    a;
  747.         vec3_t    forward, right, up;
  748.         vec3_t    temp;
  749.  
  750.         AngleVectors (ent->v.angles, forward, right, up);
  751.  
  752.         VectorCopy (start_l, temp);
  753.         start_l[0] = DotProduct (temp, forward);
  754.         start_l[1] = -DotProduct (temp, right);
  755.         start_l[2] = DotProduct (temp, up);
  756.  
  757.         VectorCopy (end_l, temp);
  758.         end_l[0] = DotProduct (temp, forward);
  759.         end_l[1] = -DotProduct (temp, right);
  760.         end_l[2] = DotProduct (temp, up);
  761.     }
  762. #endif
  763.  
  764. // trace a line through the apropriate clipping hull
  765.     SV_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);
  766.  
  767. #ifdef QUAKE2
  768.     // rotate endpos back to world frame of reference
  769.     if (ent->v.solid == SOLID_BSP && 
  770.     (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]) )
  771.     {
  772.         vec3_t    a;
  773.         vec3_t    forward, right, up;
  774.         vec3_t    temp;
  775.  
  776.         if (trace.fraction != 1)
  777.         {
  778.             VectorSubtract (vec3_origin, ent->v.angles, a);
  779.             AngleVectors (a, forward, right, up);
  780.  
  781.             VectorCopy (trace.endpos, temp);
  782.             trace.endpos[0] = DotProduct (temp, forward);
  783.             trace.endpos[1] = -DotProduct (temp, right);
  784.             trace.endpos[2] = DotProduct (temp, up);
  785.  
  786.             VectorCopy (trace.plane.normal, temp);
  787.             trace.plane.normal[0] = DotProduct (temp, forward);
  788.             trace.plane.normal[1] = -DotProduct (temp, right);
  789.             trace.plane.normal[2] = DotProduct (temp, up);
  790.         }
  791.     }
  792. #endif
  793.  
  794. // fix trace up by the offset
  795.     if (trace.fraction != 1)
  796.         VectorAdd (trace.endpos, offset, trace.endpos);
  797.  
  798. // did we clip the move?
  799.     if (trace.fraction < 1 || trace.startsolid  )
  800.         trace.ent = ent;
  801.  
  802.     return trace;
  803. }
  804.  
  805. //===========================================================================
  806.  
  807. /*
  808. ====================
  809. SV_ClipToLinks
  810.  
  811. Mins and maxs enclose the entire area swept by the move
  812. ====================
  813. */
  814. void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
  815. {
  816.     link_t        *l, *next;
  817.     edict_t        *touch;
  818.     trace_t        trace;
  819.  
  820. // touch linked edicts
  821.     for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
  822.     {
  823.         next = l->next;
  824.         touch = EDICT_FROM_AREA(l);
  825.         if (touch->v.solid == SOLID_NOT)
  826.             continue;
  827.         if (touch == clip->passedict)
  828.             continue;
  829.         if (touch->v.solid == SOLID_TRIGGER)
  830.             Sys_Error ("Trigger in clipping list");
  831.  
  832.         if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
  833.             continue;
  834.  
  835.         if (clip->boxmins[0] > touch->v.absmax[0]
  836.         || clip->boxmins[1] > touch->v.absmax[1]
  837.         || clip->boxmins[2] > touch->v.absmax[2]
  838.         || clip->boxmaxs[0] < touch->v.absmin[0]
  839.         || clip->boxmaxs[1] < touch->v.absmin[1]
  840.         || clip->boxmaxs[2] < touch->v.absmin[2] )
  841.             continue;
  842.  
  843.         if (clip->passedict && clip->passedict->v.size[0] && !touch->v.size[0])
  844.             continue;    // points never interact
  845.  
  846.     // might intersect, so do an exact clip
  847.         if (clip->trace.allsolid)
  848.             return;
  849.         if (clip->passedict)
  850.         {
  851.              if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
  852.                 continue;    // don't clip against own missiles
  853.             if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
  854.                 continue;    // don't clip against owner
  855.         }
  856.  
  857.         if ((int)touch->v.flags & FL_MONSTER)
  858.             trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
  859.         else
  860.             trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
  861.         if (trace.allsolid || trace.startsolid ||
  862.         trace.fraction < clip->trace.fraction)
  863.         {
  864.             trace.ent = touch;
  865.              if (clip->trace.startsolid)
  866.             {
  867.                 clip->trace = trace;
  868.                 clip->trace.startsolid = true;
  869.             }
  870.             else
  871.                 clip->trace = trace;
  872.         }
  873.         else if (trace.startsolid)
  874.             clip->trace.startsolid = true;
  875.     }
  876.     
  877. // recurse down both sides
  878.     if (node->axis == -1)
  879.         return;
  880.  
  881.     if ( clip->boxmaxs[node->axis] > node->dist )
  882.         SV_ClipToLinks ( node->children[0], clip );
  883.     if ( clip->boxmins[node->axis] < node->dist )
  884.         SV_ClipToLinks ( node->children[1], clip );
  885. }
  886.  
  887.  
  888. /*
  889. ==================
  890. SV_MoveBounds
  891. ==================
  892. */
  893. void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
  894. {
  895. #if 0
  896. // debug to test against everything
  897. boxmins[0] = boxmins[1] = boxmins[2] = -9999;
  898. boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999;
  899. #else
  900.     int        i;
  901.     
  902.     for (i=0 ; i<3 ; i++)
  903.     {
  904.         if (end[i] > start[i])
  905.         {
  906.             boxmins[i] = start[i] + mins[i] - 1;
  907.             boxmaxs[i] = end[i] + maxs[i] + 1;
  908.         }
  909.         else
  910.         {
  911.             boxmins[i] = end[i] + mins[i] - 1;
  912.             boxmaxs[i] = start[i] + maxs[i] + 1;
  913.         }
  914.     }
  915. #endif
  916. }
  917.  
  918. /*
  919. ==================
  920. SV_Move
  921. ==================
  922. */
  923. trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
  924. {
  925.     moveclip_t    clip;
  926.     int            i;
  927.  
  928.     memset ( &clip, 0, sizeof ( moveclip_t ) );
  929.  
  930. // clip to world
  931.     clip.trace = SV_ClipMoveToEntity ( sv.edicts, start, mins, maxs, end );
  932.  
  933.     clip.start = start;
  934.     clip.end = end;
  935.     clip.mins = mins;
  936.     clip.maxs = maxs;
  937.     clip.type = type;
  938.     clip.passedict = passedict;
  939.  
  940.     if (type == MOVE_MISSILE)
  941.     {
  942.         for (i=0 ; i<3 ; i++)
  943.         {
  944.             clip.mins2[i] = -15;
  945.             clip.maxs2[i] = 15;
  946.         }
  947.     }
  948.     else
  949.     {
  950.         VectorCopy (mins, clip.mins2);
  951.         VectorCopy (maxs, clip.maxs2);
  952.     }
  953.     
  954. // create the bounding box of the entire move
  955.     SV_MoveBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
  956.  
  957. // clip to entities
  958.     SV_ClipToLinks ( sv_areanodes, &clip );
  959.  
  960.     return clip.trace;
  961. }
  962.  
  963.